
\documentclass{beamer}

\usepackage{pgf,pgfpages}
\usepackage{graphicx}
\usepackage{units}
\usepackage{listings}
\usepackage[utf8]{inputenc}

\usepackage[variablett]{lmodern}

\newcommand*{\vttfamily}{%
  \fontencoding{T1}\fontfamily{lmvtt}\selectfont
}

\newcommand*{\textsmallunderscore}{%
  \begingroup
    \fontencoding{T1}\fontfamily{lmtt}\selectfont
    \textunderscore
  \endgroup
}

\definecolor{darkgreen}{rgb}{0,.5,0}
\renewcommand{\lstlistingname}{Code}



\mode<presentation>
{
  \usetheme{ift}
  \setbeamercovered{transparent}
  \setbeamertemplate{items}[square]
  \setbeamertemplate{caption}[numbered]
}

\usefonttheme[onlymath]{serif}
\setbeamerfont{frametitle}{size=\LARGE,series=\bfseries}
\definecolor{uibred}{RGB}{170, 0, 0}
\definecolor{uibblue}{RGB}{0, 84, 115}
\definecolor{uibgreen}{RGB}{119, 175, 0}
%\definecolor{uibgreen}{RGB}{50, 105, 0}
\definecolor{uiborange}{RGB}{217, 89, 0}
%\beamertemplatenavigationsymbolsempty
%\include{macros}
%\includeonlyframes{current}
\defbeamertemplate{enumerate item}{mycircle}
{
  %\usebeamerfont*{item projected}%
  %\usebeamercolor[bg]{item projected}%
  \begin{pgfpicture}{0ex}{0ex}{1.5ex}{0ex}
	%\pgfcircle[fill]{\pgfpoint{0pt}{.75ex}}{1.25ex}
    \pgfbox[center,base]{\color{uibblue}\insertenumlabel.}
  \end{pgfpicture}%
}
[action]
{\setbeamerfont{item projected}{size=\scriptsize}}
\setbeamertemplate{enumerate item}[mycircle]
%\lstset{
% 	language=C++,
%% 	captionpos=b,
% 	tabsize=3,
% 	frame=lines,
% 	keywordstyle=\color{blue},
% 	commentstyle=\color{gray},
% 	stringstyle=\color{green},
%	extendedchars=true,
% 	numbers=left,
% 	numberstyle=\tiny,
% 	numbersep=10pt,
% 	breaklines=true,
% 	showstringspaces=false,
% 	basicstyle=\footnotesize\ttfamily,
% 	emph={label},
% 	inputencoding=utf8,
% 	extendedchars=true,
%  literate=%
%  {é}{{\'{e}}}1
%  {è}{{\`{e}}}1
%  {ê}{{\^{e}}}1
%  {ë}{{\¨{e}}}1
%  {û}{{\^{u}}}1
%  {ù}{{\`{u}}}1
%  {â}{{\^{a}}}1
%  {à}{{\`{a}}}1
%  {î}{{\^{i}}}1
%  {ç}{{\c{c}}}1
%  {Ç}{{\c{C}}}1
%  {É}{{\'{E}}}1
%  {Ê}{{\^{E}}}1
%  {À}{{\`{A}}}1
%  {Â}{{\^{A}}}1
%  {Î}{{\^{I}}}1
%}
\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
%  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  language=C++,
%  basicstyle=\ttfamily,
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{blue}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  commentstyle=\color{darkgreen}\ttfamily,
  breaklines=true,
  columns=flexible,
  literate={_}{\textsmallunderscore}1,
%  gobble=4,
%  xleftmargin=\leftmargini, 
%  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{green},      % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 
  keywordstyle=\color{blue},       % keyword style
  morekeywords={*,function, foreach, procedure, put, pop, remove,...},
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{black}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showstringspaces=false,          % underline spaces within strings only
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mauve},    	% string literal style
%  tabsize=4,                       % sets default tabsize to 2 spaces 
  title=\lstname,                   % show the filename of files included with \lstinputlisting; also try caption instead of title
  mathescape=true
}


\title{ \textbf{Domain-based consistencies for non-binary constraints}
\vspace{1.2cm}}
\author{
\vspace{0.2cm}
\vspace{0.2cm}
Student: 
KHONG Minh Thanh \\
Supervisors: Yves Deville, Jean-Baptiste Mairy
\vspace{0.4cm}
}

\institute{
Institut de la Francophonie pour l'Informatique \\
\& beCool Constraints Group, ICTEAM/INGI, UCL
}
\date{}

\AtBeginSection[]
{
\addtocounter{framenumber}{-1}
\begin{frame}<beamer>{Table of Contents}
\tableofcontents[currentsection,currentsubsection, 
    hideothersubsections, 
    sectionstyle=show/shaded,
]
\end{frame}
}

\begin{document}
\maketitle

%
% Set the background for the rest of the slides.
% Insert infoline at the end 
%
\setbeamertemplate{background}
 {\includegraphics[width=\paperwidth,height=\paperheight]{images/slide_bg}}
\setbeamertemplate{footline}[ifttheme]

\begin{frame}
  \frametitle{Plan}
  \addtocounter{framenumber}{-1}
  \tableofcontents
\end{frame}

%--------------------------------------------------------------------
%                          Definition
%--------------------------------------------------------------------
\section{Definitions}
\begin{frame}{Definitions}
\textbf{A Constraint Satisfaction Problem (CSP)} $(X, D(X), C)$ is a composed of:
\begin{itemize}
\item a set $X = \{x_1,\dots, x_n\}$ of n variables,
\item a domain $D(X)= D(x_1)*\dots * D(x_n)$ which is the Cartesian product of the domains of the variables in X,
\item a set of constraints $C = \{c_1,\dots,c_e\}$
	\begin{itemize}
	\item a constraint $c(x_{1},.., x_{k}) \in C$ is a relation defined on the variables $x_{1},\dots, x_{k}$
	\item $c$ is denoted by $(vars(c), rel(c))$ 
	
	where $vars(c)$ = $\{x_{1},\dots,x_{k}\}$ and $rel(c)$ contains the allowed combinations of values for the variables in $vars(c)$
	\end{itemize}
%\item Binary CSP: only binary constraints (2 variables)
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Definitions}
%\textbf{Constraint Satisfaction Problem (CSP)}
%	\begin{itemize}
%	\item A constraint $c$ can be either defined \textit{extensionally} by explicitly giving $rel(c)$ (table constraints)\\
%	or \textit{intensionally} implicitly specifying $rel(c)$ through a arithmetic function 
%	\item Two constraints $c_i, c_j$ \textit{intersect} iff $vars(c_i) \cap vars(c_j) \neq \emptyset$
%	\end{itemize}
	
For a constraints $c(x_{1},\dots ,x_{k}) \in C$ 
	\begin{itemize}
	\item A tuple $\tau \in rel(c)$ is an order list of values $(a_{1},\dots,a_{k})$
	\item A tuple $\tau$ is \textit{valid} iff all the values in the tuple are present in the domain of the corresponding variables
	\end{itemize}
Two constraints $c_i, c_j$ \textit{intersect} iff $vars(c_i) \cap vars(c_j) \neq \emptyset$


\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Definitions}
	\begin{itemize}
%	\item The assignment of a value \textit{a} to variable $x_i$ is denoted by $(x_i, a)$
	\item Any tuple $\tau= (a_1,\dots,a_k)$ can be viewed as a set of value to variable assignments $\{(x_1,a_1),\dots, (x_k, a_k)\}$, and $vars(\tau) = \{x_1,\dots, x_k\}$
%	\item The ordered set of variables over which a tuple $\tau$ is defined is $vars(\tau)$
	\item For any subset $vars'$ of $vars(\tau)$, $\tau[vars']$ is the sub-tuple of $\tau$ that includes only assignments to the variables in $vars'$
	\item For two tuples $\tau$ and $\tau'$ over $vars(c) = (x_1, \dots, x_k)$: 
	$\tau <_l \tau'$ 
	
	iff there exists a subsequence $(x_1,\dots, x_j)$ of $vars(c)$ such that $\tau[x_1,\dots,x_j] = \tau'[x_1,\dots,x_j]$ and $\tau[x_{j+1}] <_l \tau'[x_{j+1}]$
	\item An assignment $\tau$ is consistent iff $\forall c_i$, where $vars(c_i) \subseteq vars(\tau),$ $\tau[vars(c_i)] \in rel(c_i)$
	\end{itemize}
\end{frame}
%--------------------------------------------------------------------


%--------------------------------------------------------------------
%                        Generalized Arc Consistency
%--------------------------------------------------------------------
\section{Generalized Arc Consistency (GAC)}
\begin{frame}{Generalized Arc Consistency}
\textbf{Generalized Arc Consistency (GAC)}
	\begin{itemize}
	\item 
	A CSP $(X, D(X), C)$ is \textit{generalized arc consistent} iff $\forall x_i \in X, D(x_i)$ is non-empty and $\forall a \in D(x_i), a$ is \textit{GAC-supported} in each constraint $c_j$, s.t. $x_i \in vars(c_j)$.\\
	A value $a \in D(x_i)$ is \textit{GAC-supported} in a contraint $c_j$ iff $\exists \tau \in rel(c_j)$ such that $\tau[x_i]=a$ and $\tau$ is valid. In this case, we say that $\tau$ is a \textit{GAC-support} of $a$ in $c_j$.
	\end{itemize}
\textbf{Algorithm}	
	\begin{itemize}
	\item 
	\textbf{GAC2001/3.1} time complexity: $O(ek^2d^k)$ space complexity: extensional constraint $O(ekd)$  \cite{domain:2008}
%	\item Combine \textbf{PWC} with \textbf{GAC} we have: \textbf{PWC + GAC}. \cite{domain:2008}
	\end{itemize}
\end{frame}
%--------------------------------------------------------------------

%%--------------------------------------------------------------------
%%                        Constraint-based consistencies
%%--------------------------------------------------------------------
%\section{Constraint-based consistencies}
%\begin{frame}{Constraint-based consistencies}
%	\begin{itemize}
%	\item Relational (i,m)-Consistency
%	\item Strong Relational (i,m)-Consistency
%	\item Relational (i,m)-Consistency
%	\item Strong Relational (i,m)-Consistency
%	\end{itemize}
%\end{frame}
%%--------------------------------------------------------------------
%\begin{frame}{Constraint-based consistencies}
%Relational (i,m)-Consistency
%	\begin{itemize}
%	\item A CSP $(X, D(X), C)$ is \textit{ relational (i,m)-consistent} iff any consistent assignment for $i$ variables in a set of $m$ constraints can be extended to all the variables in the set.
%	\end{itemize}
%Strong Relational (i,m)-Consistency
%	\begin{itemize}
%	\item A CSP $(X, D(X), C)$ is \textit{\textbf{strong} relational (i,m)-consistent} iff 
%	it is relational (j,m)-consistent for every $j \leq i$.
%	\end{itemize}
%
%\end{frame}
%%--------------------------------------------------------------------
%\begin{frame}{Constraint-based consistencies}
%Pairwise Consistency \textbf{(PWC)}
%	\begin{itemize}
%	\item
%	A CSP $(X, D(X), C)$ is \textit{pairwise consistent} iff it has non-empty relations and any consistent tuple $\tau$ of a constraint $c$ can be consistently extended to any other constraint that intersects with $c$.
%	\end{itemize}
%k-Wise Consistency \textbf{(kWC)}
%	\begin{itemize}
%	\item A CSP $(X, D(X), C)$ is \textit{k-wise consistent} iff any consistent tuple for a constraint can be consistently extended to any $k-1$ other constraints.
%	\end{itemize}	
%
%\end{frame}
%%--------------------------------------------------------------------



%--------------------------------------------------------------------
%		                  Domain-based consistencies
%--------------------------------------------------------------------
\section{Consistencies stronger than GAC}
\begin{frame}{Consistencies stronger than GAC}
	\begin{itemize}
	\item Restricted Pairwise Consistency \textbf{(RPWC)}
	\item Relational Path Inverse Consistency \textbf{(rPIC)}
	\item Max Restricted Pairwise Consistency \textbf{(Max-RPWC)}
	\item Relational Neighborhood Inverse Consistent \textbf{(rNIC)}
	\item Singleton Generalized Arc Consistency \textbf{(SGAC)}
	\item \textbf{PWC + GAC}
	\item Comparison
	\end{itemize}
\end{frame}
%--------------------------------------------------------------------
%\subsection{Some domain-based consistencies}
\begin{frame}{Restricted Pairwise Consistency}
\textbf{Restricted Pairwise Consistency \textbf{(RPWC)}}
	\begin{itemize}
	\item A non-binary CSP $(X, D(X), C)$ is \textit{restricted pairwise consistent} iff $\forall x_i \in X,$ all values in $D(x_i)$ is GAC and, $\forall a \in D(x_i), \forall c_j \in C,$ $x_i \in vars(c_j),$ s.t. there exists a unique valid $\tau \in rel(c_j)$ with $\tau[x_i] = a$ \textbf{and} \\
	$\forall c_k \in C,$ s.t. $vars(c_j) \cap vars(c_k) \neq \emptyset,$ $\exists \tau' \in rel(c_k),$ s.t. $\tau[vars(c_j) \cap vars(c_k)]= \tau'[vars(c_j) \cap vars(c_k)]$ and $\tau'$ is valid.
	\end{itemize}
\textbf{Algorithms}
	\begin{itemize}
	\item \textbf{RPWC-1} time complexity: $O(ne^2k^2d^k)$ space complexity: $O(ekd)$  \cite{domain:2008}
	\end{itemize}
\textbf{RPWC} is strictly stronger than \textbf{GAC} \cite{domain:2008}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Restricted Pairwise Consistency}
\textbf{Example}
	\begin{itemize}
	\item $D(x_1)=D(x_2)=D(x_3)=\{1,2,3\}$
	\item $c_1=alldiff(x_1,x_2,x_3)$, $c_2=x_1=x_2$
	\end{itemize}
The CSP is \textbf{GAC} but is not \textbf{RPWC} ($(x_1,1), (x_1,2), (x_1,3), (x_2,1), (x_2,2), (x_2,3)$ is not RPWC)
\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}{relational Path Inverse Consistency}
\textbf{relational Path Inverse Consistency \textbf{(rPIC)}}
	\begin{itemize}
	\item A non-binary CSP $(X, D(X), C)$ is \textit{relational path inverse consistent} iff $\forall x_i \in X, \forall c_j \in C,$ where $x_i \in vars(c_j)$, and $\forall c_k \in C,$ s.t $vars(c_j) \cap vars(c_k) \neq \emptyset,$ $\exists \tau \in rel(c_j)$ such that $\tau[x_i]=a$, $\tau$ is valid, \textbf{and} $\exists \tau' \in rel(c_k)$ such that $\tau[vars(c_j)\cap vars(c_k)] = \tau'[vars(c_j)\cap vars(c_k)]$ and $\tau'$ is valid.
	\end{itemize}
\textbf{Algorithms}
	\begin{itemize}
	\item \textbf{rPIC-1} time complexity: $O(e^2k^2d^p)$ space complexity: $O(e^2kd)$ \cite{domain:2008} \\
	$p$ is the maximum number of variables involved in two constraints sharing at least two variables.
	\end{itemize}
\textbf{rPIC} is strictly stronger than \textbf{RPWC} \cite{domain:2008}

\end{frame}
%--------------------------------------------------------------------
\begin{frame}{relational Path Inverse Consistency}
\textbf{Example}
	\begin{itemize}
	\item $D(x_1)=D(x_2)=D(x_3)=\{0,1,2\}$, $D(x_4)=\{0,1\}$
	\item $c_1=alldiff(x_1,x_2,x_3), c_2=alldiff(x_2,x_3,x_4)$
	\end{itemize}

This CSP is \textbf{RWPC} but is not \textbf{rPIC} because no GAC-support of $(x_1,2)$ on $c_1$ can be extended to $c_2$
\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}{Max Restrited Pairwise Consistency}
\textbf{Max Restrited Pairwise Consistency \textbf{(Max-RPWC)}} \cite{domain:2008}
	\begin{itemize}
	\item 	A non-binary CSP $(X, D(X), C)$ is \textit{max restricted pairwise consistent} iff $\forall x_i \in X,$ $\forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a$, $\tau$ is valid, \textbf{and} $\forall c_k \in C,$ s.t. $vars(c_j) \cap vars(c_k) \neq \emptyset, \exists \tau' \in rel(c_k),$ s.t. $\tau[vars(c_j) \cap vars(c_k)]= \tau'[vars(c_j) \cap vars(c_k)]$ and $\tau'$ is valid.
	\end{itemize}
\textbf{Algorithms}
	\begin{itemize}
	\item \textbf{Max-RPWC-1} complexity of time: $O(e^2k^2d^p)$, of space: $O(ekd)$
	\item \textbf{Max-RPWC-2} complexity of time: $O(e^2k^2d^k)$, of space: $O(e^2kd^f)$\\
	  $f$ is the maximum number of intersecting variables on two constraints
	\item \textbf{Max-RPWC-3} complexity of time: $O(e^2k^2d^p)$, of space: $O(e^2kd)$ 
	\end{itemize}
\textbf{Max-RPWC} is strictly stronger than \textbf{rPIC}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Max Restrited Pairwise Consistency}
\textbf{Example}
\begin{itemize}
\item $D(x_1)=D(x_2)=D(x_3)=\{0,1\}$, $D(x_4)= D(x_5)=\{0\}$
%\item Three constraints $c_1,c_2,c_3$ are showed in the figure below
\end{itemize}
Three constraints $c_1,c_2,c_3$ are showed in the figure below
	\begin{figure}[ht]
		\includegraphics[height=4cm]{./images/MaxRPWC_rPIC2.png}
		\caption{This CSP is rPIC but is not Max-RPWC. Because non of GAC-supports of $(x_1,0)$ on $c_1$ can be extended to both $c_2$ and $c_3$.}
	\end{figure}
\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}{\Large relational Neighborhood Inverse Consistent}
\textbf{relational Neighborhood Inverse Consistent \textbf{(rNIC)}}
		\begin{itemize}
		\item A CSP $(X, D(X), C)$ is \textit{relational neighborhood inverse consistent} iff 
		$\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and} $\tau$ can be extended to a solution of the subproblem consisting of the set of variables $X_j= \{vars(c_j)\cup vars(c_{j_1})\cup\dots\cup vars(c_{j_m})\},$ where $c_{j_1},\dots,c_{j_m}$ are the constraints that intersect with $c_j$.
%		\textbf{rNIC} is incomparable to \textbf{Max-R3WC} \cite{strong domain:2008}
		\end{itemize}
\textbf{rNIC} is strictly stronger than \textbf{MaxRPWC} \cite{strong domain:2008}
\end{frame}
%--------------------------------------------------------------------
%\begin{frame}{\Large relational Neighborhood Inverse Consistent}
%\textbf{Example}
%
%\textbf{manque exemple}
%
%\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}{PWC+GAC}
\textbf{PWC+GAC} \cite{domain:2008}
	\begin{itemize}
	\item 	\textbf{Pairwise Consistency} \textbf{(PWC)}\\
	A CSP $(X, D(X), C)$ is \textit{pairwise consistent} iff it has non-empty relations and any consistent tuple $\tau$ of a constraint $c_i$ can be consistently extended to any other constraint that intersects with $c_i$.
	\item \textbf{PWC + GAC}: 
		\begin{itemize}
		\item PWC deletes tuples from constraint relations
		\item GAC is applied for the domain filtering: values that have lost all their GAC-supports in a constraint will be deleted
		\end{itemize}
	\end{itemize}
\textbf{PWC+GAC} is strictly stronger than \textbf{Max-RPWC} \cite{domain:2008}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{PWC+GAC}
\textbf{Example}
	\begin{itemize}
	\item $D(x_1)=D(x_2)=D(x_3)=D(x_4)=D(x_5)=\{0,1\}, D(x_6)=\{0\}$
	\item All three constraint are showed in the figure below
	\end{itemize}
	\begin{figure}[ht]
		\includegraphics[height=3.3cm]{./images/PWC_GAC_MaxRPWC2.png}
		\caption{This CSP is Max-RPWC but is not PWC+GAC. Because PWC will delete tuple (0,0,0,0) in $c_2$ and then tuple (0,0,0) in $c_1$, $(x_1,0)$ will be removed.}
	\end{figure}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Singleton Generalized Arc Consistency}
\textbf{Singleton Generalized Arc Consistency \textbf{(SGAC)}}
	\begin{itemize}
		\item A CSP $(X, D(X), C)$ is \textit{singleton generalized arc consistent} iff it has non-empty domain and for any assignment of a variable, the resulting subproblem $(X, D(X)_{x=a}, C)$ is \textit{GAC}.
	\end{itemize}
\textbf{SGAC} is strictly stronger than \textbf{RPWC} \cite{domain:2008}\\
\textbf{SGAC} is incomparable with \textbf{rPIC}, \textbf{Max-RPWC}, \textbf{PWC+GAC}\cite{domain:2008}\\
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{ Singleton Generalized Arc Consistency}
\textbf{Example}\\
\textbf{SGAC} $\longrightarrow$ \textbf{RPWC}
	\begin{itemize}
	\item $D(x_1)=D(x_2)=D(x_3)=\{0,1\}$
	\item $c_1= x_1\neq x_2, c_2= x_2\neq x_3, c_3= x_3\neq x_1$
	\end{itemize}
This CSP is RPWC but is not SGAC ($(X,D(X)_{x_1=0},C)$ is not GAC).
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Singleton Generalized Arc Consistency}
\textbf{rPIC, Max-RPWC, PWC+GAC} is not stronger than \textbf{SGAC}
	\begin{itemize}
	\item $D(x_1)=D(x_2)=D(x_3)=\{0,1\}$
	\item $c_1= x_1\neq x_2, c_2= x_2\neq x_3, c_3= x_3\neq x_4, c_4= x_4 = x_1$
	\item This CSP is rPIC, Max-RPWC, PWC+GAC but is not SGAC.\\
	$(X,D(X)_{x_1=0},C)$ is not GAC.
	\end{itemize}
\textbf{SGAC} is not stronger than \textbf{rPIC, Max-RPWC, PWC+GAC}
	\begin{itemize}
	\item $D(x_1)=D(x_2)=D(x_3)=\{0,1\}$
	\item $c_1(x_1,x_2, x_3) = \{000,011,100,111\},$ $c_2(x_1,x_2,x_3)=\{001,010,100,111\}$
	\item This CSP is SGAC but is not rPIC, Max-RPWC, PWC+GAC.\\
	non of GAC-supports of $(x_1,0)$ on $c_1$ can satisfy $c_2$.
	\end{itemize}
$\Longrightarrow$ \textbf{SGAC} is incomparable with \textbf{rPIC, Max-RPWC, PWC+GAC}\\
\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}{Comparison}
Follow \cite{domain:2008}, we have a figure of comparison:

	\begin{figure}[ht]
	  	\begin{center}
		\includegraphics[height=1.5cm]{./images/comparison_non_binary2.png}
		\caption{Summary of the comparison between domain-based consistencies for non-binary constraints}
		\end{center}
	\end{figure}
%For the full proofs, we can find it in \cite{domain:2008}.
\end{frame}



%--------------------------------------------------------------------
%                		Other domain-based consistencies
%--------------------------------------------------------------------
\section{Other consistencies stronger than GAC}
%--------------------------------------------------------------------
\begin{frame}{Other domain-based consistencies}
	\begin{itemize}
	\item Max Restricted 3-wise Consistency \textbf{(Max-R3WC)}
	\item Max Restricted k-wise Consistency \textbf{(Max-RkWC)}
	\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Max Restricted 3-wise Consistency}
\textbf{Max Restricted 3-wise Consistency (Max-R3WC)} 
	\begin{itemize}
	\item A CSP $(X, D(X), C)$ is \textit{max restricted 3-wise consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid, \textbf{and} $\forall c_k, c_l \in C$ there exists valid tuples $\tau' \in rel(c_k), \tau'' \in rel(c_l)$ s.t. 
	$\tau[vars(c_j)\cap vars(c_k)] = \tau'[vars(c_j)\cap vars(c_k)],$ 
	$\tau[vars(c_j)\cap vars(c_l)]=\tau''[vars(c_j)\cap vars(c_l)],$
	$\tau'[vars(c_k)\cap vars(c_l)]=\tau''[vars(c_k)\cap vars(c_l)]$.
	\end{itemize}
\textbf{Algorithms}
	\begin{itemize}
	\item \textbf{R3WC-1} time complexity: $O(e^3k^3d^{p+p'})$ space complexity: extensional constraint $O(ekd)$ \cite{strong domain:2008}\\
	$p+p'$: total number of variables involved in 3 constraints
	\end{itemize}
\textbf{Max-R3WC} is strictly stronger than \textbf{Max-RPWC}

	\textbf{Max-R3WC} is incomparable to \textbf{rNIC} \cite{strong domain:2008}
	
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Max Restricted k-wise Consistency}
\textbf{Max Restricted k-wise Consistency (Max-RkWC)}
	\begin{itemize}
	\item A CSP $(X, D(X), C)$ is \textit{max restricted k-wise consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_j \in C,$ where $x_i \in vars(c_j), \exists \tau \in rel(c_j)$ such that $\tau[x_i]=a, \tau$ is valid,\\ \textbf{and}
	for any set of additional $k-1$ constraints $c_1, \dots, c_{k-1}, \tau$ can be extend to a valid instantiation on variables $\bigcup_{m=1}^{k-1}vars(c_m)$ that satisfies each $c_m$ for $m=1,\dots,k-1$.
%		\item[+] Algorithms:\\ \textbf{non algo}
	\end{itemize}
\textbf{Max-RkWC} is strictly stronger than \textbf{Max-R3WC}
\end{frame}
%--------------------------------------------------------------------


%--------------------------------------------------------------------
%                				Algorithms
%--------------------------------------------------------------------
\section{Algorithms}
\begin{frame}{Algorithms}
	\begin{itemize}
	\item Generic algorithm
	\item Max-RPWC-1
	\item rPIC-1
	\item RPWC-1
	\item Max-RPWC-2
	\item Max-RPWC-3
	\item Summary
	\end{itemize}
\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}[fragile]{Generic algorithm}
\begin{lstlisting}[caption= function DFcons]
function DFcons($CSP,DFC$, current-var)
  if current-var = -1, put all constraints in Q;
  else Enqueue(current-var, -1);
  while Q is not empty
     pop constraint $c_i$ from Q;
     foreach unassigned variable $x_j$ where $x_j \in vars(c_i)$
     if Revise($x_j, c_i,DFC$) $> 0$
        if D($x_j$) is empty return INCONSISTENCY;
        Enqueue($x_j, c_i$);
  return CONSISTENCY;
\end{lstlisting}

$CSP$: the CSP to filtering domain\\
$DFC$: the method of filtering (Max-RPWC, RPWC, rPIC)\\
\textit{current-var}: if algorithm
{\footnotesize
\begin{itemize}
\item is used standalone, \textit{current-var} = -1, put all constraint in Q (line 2)
\item is applied during search, \textit{current-var} = currently assigned variable,\\ put only constraints associated with \textit{current-var} (line 3)
\end{itemize}
}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}[fragile]{Generic algorithm}
\begin{lstlisting}[caption= procedure Enqueue]
procedure Enqueue($x_j, c_i$)
   foreach $c_m$ s.t. $x_j \in vars(c_m)$
      put in Q each $c_l(\neq c_i)$ s.t. $|vars(c_l) \cap vars(c_m)| > 1$;
      if $c_m \neq c_i$ put $c_m$ in Q;
\end{lstlisting}
When some value of $x_j$ is removed, add the constraints $c_m$ ($x_j \in vars(c_m)$) in Q and add other constraints $c_l$ that intersect with $c_m$
{\footnotesize
	\begin{itemize}
	\item because a tuple $\tau \in rel(c_m), \tau[x_j]=a$ may be the PW-support of $\tau' \in rel(c_l)$
	\end{itemize}
}
\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}[fragile]{Max-RPWC-1}
\begin{lstlisting}[caption=function Revise of Max-RPWC-1]
function Revise($x_j, c_i,MaxRPWC$)
   for each value $a \in D(x_j)$
      PW $\leftarrow$ FALSE;
      foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
         PW $\leftarrow$ TRUE;
         for each $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
            if $\nexists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau' [vars(c_i) \cap vars(c_m)]$
               PW $\leftarrow$ FALSE; break;
         if PW = TRUE $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
      if PW = FALSE remove $a$ from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}
{\footnotesize
Line 4-10: for each valid tuple $\tau \in rel(c_m), \tau[x_j]=a$, check if it can be extended to each constraint intersecting with $c_m$. If not, remove $a$ from $D(x_j)$.\\
Line 6-7: for each constraint $c_m$, check if $\tau$ has PW-support $\tau'$ in $c_m$.
}
\end{frame}

%--------------------------------------------------------------------
\begin{frame}[fragile]{Max-RPWC-1}
\textbf{Max-RPWC-1}
\begin{itemize}
\item Time complexity: $O(e^2k^2d^p)$, $p$ is the maximum number of variables involved in two constraints sharing at least two variables.
\item Space complexity: $O(ekd)$
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
%------------------------------rPIC----------------------------------
%--------------------------------------------------------------------
\begin{frame}[fragile]{rPIC-1}
\begin{lstlisting}[caption= function Revise of rPIC-1]
function Revise($x_j,c_i,rPIC$)
   foreach value $a \in D(x_j)$
      foreach $c_m$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
         PW $\leftarrow$ FALSE;
         foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i,c_m}$ s.t. $\tau[x_j] = a$
            if $\exists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau'[vars(c_i) \cap vars(c_m)]$
               $lastGAC_{x_j,a,c_i,c_m} \leftarrow \tau$;
               PW $\leftarrow$ TRUE; break;
         if PW = FALSE remove $a$ from $D(x_j)$; break;
   return number of deleted values;
\end{lstlisting}
{\footnotesize
Line 2-9: for each $a \in D(x_j)$, for each pair of intersecting constraints $(c_i, c_m)$, check if exist a pair of tuples $\tau \in rel(c_i), \tau' \in rel(c_m),$ s.t. $\tau'$ is PW-support for $\tau$. If not, remove $a$ from $D(x_j)$
}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}[fragile]{rPIC-1}
\textbf{rPIC-1:}
\begin{itemize}
\item Time complexity: $O(e^2k^2d^p)$
\item Space complexity: $O(e^2kd)$
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
%----------------------------RPWC------------------------------------
%--------------------------------------------------------------------
\begin{frame}[fragile]{RPWC}
\begin{lstlisting}[caption=function Revise of RPWC-1]
function Revise($x_j,c_i,RPWC$)
   foreach value $a \in D(x_j)$
      if $lastGAC2_{x_j,a,c_i} \neq NIL$ and $lastGAC2_{x_j,a,c_i}$ is not valid
         if $\exists$ valid $\tau (\in rel(c_i)) \geq_l lastGAC2_{x_j,a,c_i}$ s.t. $\tau [x_j] = a$
            $lastGAC2_{x_j,a,c_i} \leftarrow \tau$;
         else $lastGAC2_{x_j,a,c_i} \leftarrow NIL$;
      if $lastGAC2_{x_j,a,c_i} \neq NIL$ and $lastGAC1_{x_j,a,c_i}$ is not valid
         $lastGAC1_{x_j,a,c_i} \leftarrow lastGAC2_{x_j,a,c_i}$;
         if $\exists$ valid $\tau (\in rel(c_i)) \geq_l lastGAC2_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
            $lastGAC2_{x_j,a,c_i} \leftarrow \tau$;
         else $lastGAC2_{x_j,a,c_i} \leftarrow NIL$;
      if $lastGAC1_{x_j,a,c_i}$ is not valid $PW \leftarrow FALSE$;
      else if $lastGAC2_{x_j,a,c_i} = NIL$
         PW $\leftarrow$ FindPWsupports($c_i,lastGAC1_{x_j,a,c_i}$);
      else PW = TRUE;
      if PW = FALSE remove a from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}
{\footnotesize
Line 2-14: for each $a \in D(x_j)$, check if it has unique GAC-supports in $c_i$. If true, find PW-support of this GAC-support in each constraint intersecting with $c_i$ (line 14).
}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}[fragile]{RPWC}
\begin{lstlisting}[caption=function FindPWsupports of RPWC-1]
function FindPWsupports($c_i,\tau$)
   PW $\leftarrow$ TRUE;
   foreach $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
      if $\nexists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i ) \cap vars(c_m)] = \tau'[vars(c_i) \cap vars(c_m)]$
         PW $\leftarrow$ FALSE; break;
   return PW;
\end{lstlisting}
{\footnotesize
Line 3-5: check if a tuple $\tau \in rel(c_i)$ has PW-support in each constraint intersecting with $c_i$.
}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}[fragile]{RPWC}
\textbf{RPWC-1:}
\begin{itemize}
\item Time complexity: $O(ne^2k^2d^k)$
\item Space complexity: $O(ekd)$
\end{itemize}

\end{frame}
%--------------------------------------------------------------------
%-----------------------------Max-RPWC-2-----------------------------
%--------------------------------------------------------------------
\begin{frame}[fragile]{Max-RPWC-2}
\begin{lstlisting}[caption= function Revise of Max-RPWC-2]
function Revise($x_j,c_i, MaxRPWC$)
   foreach value $a \in D(x_j)$
      PW $\leftarrow$ FALSE;
      foreach valid $\tau (\in rel(c_i )) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
         PW $\leftarrow$ TRUE;
         foreach $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
            $s \leftarrow \tau[vars(c_i) \cap vars(c_m)]$;
            if $lastPW_{c_i,c_m,s} \neq NIL$
               if $\exists$ valid $\tau' (\in rel(c_m )) \geq_l lastPW_{c_i,c_m,s}$ and $\tau'[vars(c_i) \cap vars(c_m)] = s$
                  $lastPW_{c_i,c_m,s} \leftarrow \tau'$;
               else
                  $lastPW_{c_i,c_m,s} \leftarrow NIL$;
                  PW $\leftarrow$ FALSE; break;
            else PW $\leftarrow$ FALSE; break;
         if PW = TRUE, $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
      if PW = FALSE, remove $a$ from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}
{\footnotesize
For each constraint $c_i$, Max-RPWC-2 keeps a set of $d^f$ pointers \{$lastPW_{c_i,c_m,s}$\} for every constraint $c_m$ intersecting with $c_i$. 

}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}[fragile]{Max-RPWC-2}
\textbf{Max-RPWC-2}
\begin{itemize}
\item Time complexity: $O(e^2k^2d^k)$
\item Space complexity: $O(ekd^f)$, where $f$ is the maximum number of intersecting variables on two constraints
\end{itemize}
\textbf{Max-RPWC-2} is not practical when the number of sharing variables is large.
\end{frame}
%%--------------------------------------------------------------------
%\begin{frame}[fragile]{Max-RPWC-2}
%\textbf{Example}
%
%\end{frame}
%--------------------------------------------------------------------
%-----------------------------Max-RPWC-3-----------------------------
%--------------------------------------------------------------------
\begin{frame}[fragile]{Max-RPWC-3}
\begin{lstlisting}[caption= function Revise of Max-RPWC-3]
function Revise($x_j,c_i,MaxRPWC$)
   foreach value $a \in D(x_j)$
      PW $\leftarrow$ FALSE;
      foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
         PW $\leftarrow$ TRUE;
         foreach $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
            if $\tau = lastGAC_{x_j,a,c_i}$, $t \leftarrow lastPW_{x_j,a,c_i,c_m}$;
            else $t \leftarrow$ first tuple in $rel(c_m)$;
            if $\nexists$ valid $\tau'(\in rel(c_m)) \geq_l t$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau'[vars(c_i) \cap vars(c_m)]$
               PW $\leftarrow$ FALSE; break;
            else $lastPW_{x_j,a,c_i,c_m} \leftarrow \tau'$;
         if PW = TRUE, $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
      if PW = FALSE, remove $a$ from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}
{\footnotesize
Max-RPWC stores a pointer $lastPW_{x_j,a,c_i,c_m}$ for each pair of intersecting constraints $c_i,c_m$
}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}[fragile]{Max-RPWC-3}
\textbf{Max-RPWC-3}
\begin{itemize}
\item Time complexity: $O(e^2k^2d^p)$ but in practice Max-RPWC-3 is better than Max-RPWC-1
\item Space complexity: $O(e^2kd)$
\end{itemize}

\end{frame}
%%--------------------------------------------------------------------
%\begin{frame}[fragile]{Max-RPWC-3}
%\textbf{Example}
%\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}[fragile]{Summary of algorithms}
	\begin{table}[h]\footnotesize
		\begin{tabular}{ | l | l | l |}
		\hline
		\textbf{Algorithm} & \textbf{Time complexity} & \textbf{Space complexity} \\ 
		\hline
		GAC3.1/2001 & $O(ek^2d^k)$ & $O(ekd)$ \\ 
		\hline
		RPWC-1 & $O(e^2k^2d^p)$ & $O(ekd)$ \\ 
		\hline
		rPIC-1 & $O(e^2k^2d^p)$ & $O(e^2kd)$ \\ 
		\hline
		MaxRPWC-1 & $O(e^2k^2d^p)$ & $O(ekd)$ \\
		\hline
		MaxRPWC-2 & $O(e^2k^2d^k)$ & $O(ekd^f)$ \\
		\hline
		MaxRPWC-3 & $O(e^2k^2d^p)$ & $O(e^2kd)$ \\
		\hline
		\end{tabular}
	\caption{Summary of algorithms for domains-based consistencies}
	\end{table}
\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\section*{Références}
\begin{frame}
\begin{thebibliography}{9}
\frametitle{References}
%\bibitem{materiel} Documents in the course
%\bibitem{domain:2001} Debruyne, Romuald, and Christian Bessiére. "Domain filtering consistencies." J. Artif. Intell. Res. (JAIR) 14 (2001): 205-230.
%\bibitem{handbook:2005} Bessiere, Christian. "Constraint propagation." Handbook of constraint programming (2006): 29-83.
\bibitem{domain:2008} Bessiere, Christian, Kostas Stergiou, and Toby Walsh. "Domain filtering consistencies for non-binary constraints." Artificial Intelligence 172.6 (2008): 800-822.
\bibitem{Inverse:2006} Stergiou, Kostas, and Toby Walsh. "Inverse Consistencies for Non-Binary Constraints." FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICATIONS 141 (2006): 153.

\bibitem{strong inverse:2007} Stergiou, Kostas. "Strong Inverse Consistencies for Non-Binary CSPs." Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on. Vol. 1. IEEE, 2007.

\bibitem{strong domain:2008} Stergiou, Kostas. "STRONG DOMAIN FILTERING CONSISTENCIES FOR NON-BINARY CONSTRAINT SATISFACTION PROBLEMS." International Journal on Artificial Intelligence Tools 17.05 (2008): 781-802.
\end{thebibliography}
\end{frame}
%--------------------------------------------------------------------
\section*{}
\begin{frame}
\begin{center}
\huge Thank you!
\end{center}

\end{frame}
\end{document}